﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace BinarySearchTree
{
    class BinarySearchTree<T> : IEnumerable<T>, ICloneable where T : IComparable
    {

        private class TreeNode
        {
            public T value;
            public TreeNode LeftChild;
            public TreeNode RightChild;

            public TreeNode(T value)
            {
                this.value = value;
                this.LeftChild = null;
                this.RightChild = null;
            }
        }

        private enum ChildType
        {
            LeftChild,
            RightChild
        }

        private TreeNode treeRoot;
        private int count;

        public int Count
        {
            get
            {
                return count;
            }
        }

        public BinarySearchTree()
        {
            this.treeRoot = null;
            this.count = 0;
        }

        public T this[int index]
        {
            get
            {
                if (index < 0 || index > this.count - 1)
                {
                    throw new IndexOutOfRangeException(string.Format("The index is not in the range [0, {0}].", this.count - 1));
                }
                TreeNode nodeAtIndex = null;
                this.FindNodeByIndex(this.treeRoot, ref index, ref nodeAtIndex);
                return nodeAtIndex.value;
            }
        }

        public void Add(T element)
        {
            Add(ref this.treeRoot, element);
            this.count++;
        }

        public bool Contains(T value)
        {
            TreeNode nodeFound = this.FindNodeByValue(this.treeRoot, value);

            if (nodeFound == null)
            {
                return false;
            }
            else
            {
                return true;
            }
        }

        public bool Remove(T value)
        {
            bool removeExecuted = this.TryRemove(ref this.treeRoot, value);
            if (removeExecuted)
            {
                this.count--;
            }
            return removeExecuted;
        }

        public void RemoveAt(int index)
        {
            if (index < 0 || index > this.count - 1)
            {
                throw new IndexOutOfRangeException(string.Format("The index is not in the range [0, {0}].", this.count - 1));
            }

            TreeNode nodeAtIndex = null;
            this.FindNodeByIndex(this.treeRoot, ref index, ref nodeAtIndex);
            TreeNode nodeAtIndexParent = this.FindNodeParentByNode(this.treeRoot, nodeAtIndex);

            if (nodeAtIndexParent == null)
            {
                this.RemoveByNode(ref this.treeRoot);
            }
            else
            {
                if (nodeAtIndex.value.CompareTo(nodeAtIndexParent.value) > 0)
                {
                    this.RemoveByNode(ref nodeAtIndexParent.RightChild);
                }
                else
                {
                    this.RemoveByNode(ref nodeAtIndexParent.LeftChild);
                }
            }
            this.count--;
        }

        private bool TryRemove(ref TreeNode root, T value)
        {
            if (root == null)
            {
                return false;
            }

            if (value.CompareTo(root.value) == 0)
            {
                this.RemoveByNode(ref root);
                return true;
            }
            else
            {
                if (value.CompareTo(root.value) > 0)
                {
                    bool removeExecuted = this.TryRemove(ref root.RightChild, value);
                    return removeExecuted;
                }
                else
                {
                    bool removeExecuted = this.TryRemove(ref root.LeftChild, value);
                    return removeExecuted;
                }
            }
        }

        private void Add(ref TreeNode node, T value)
        {
            if (node == null)
            {
                node = new TreeNode(value);
            }
            else
            {
                if (value.CompareTo(node.value) > 0)
                {
                    Add(ref node.RightChild, value);
                }
                else
                {
                    Add(ref node.LeftChild, value);
                }
            }
        }

        private TreeNode FindNodeByValue(TreeNode node, T value)
        {
            if (node == null)
            {
                return null;
            }

            if (value.CompareTo(node.value) == 0)
            {
                return node;
            }

            if (value.CompareTo(node.value) > 0)
            {
                return FindNodeByValue(node.RightChild, value);
            }

            if (value.CompareTo(node.value) < 0)
            {
                return FindNodeByValue(node.LeftChild, value); ;
            }

            return null;
        }

        private TreeNode FindNodeParentByValue(TreeNode node, T value)
        {
            if (node == null)
            {
                return null;
            }

            if (value.CompareTo(node.value) > 0)
            {
                if (node.RightChild == null)
                {
                    return null;
                }
                else
                {
                    if (value.CompareTo(node.RightChild.value) == 0)
                    {
                        return node;
                    }
                    else
                    {
                        return FindNodeParentByValue(node.RightChild, value);
                    }
                }
            }
            else
            {
                if (node.LeftChild == null)
                {
                    return null;
                }
                else
                {
                    if (value.CompareTo(node.LeftChild.value) == 0)
                    {
                        return node;
                    }
                    else
                    {
                        return FindNodeParentByValue(node.LeftChild, value);
                    }
                }
            }
        }

        private TreeNode FindNodeParentByNode(TreeNode root, TreeNode node)
        {
            if (root == null)
            {
                return null;
            }

            if (root.LeftChild == node || root.RightChild == node)
            {
                return root;
            }

            if (node.value.CompareTo(root.value) > 0)
            {
                return this.FindNodeParentByNode(root.RightChild, node);
            }
            else
            {
                return this.FindNodeParentByNode(root.LeftChild, node);
            }
        }

        private TreeNode FindSmallestNodeParent(TreeNode node)
        {
            if (node == null)
            {
                return null;
            }

            if (node.LeftChild == null)
            {
                return null;
            }

            if (node.LeftChild.LeftChild == null)
            {
                return node;
            }

            return FindSmallestNodeParent(node.LeftChild);
        }

        private void FindNodeByIndex(TreeNode root, ref int index, ref TreeNode nodeAtIndex)
        {
            if (root == null)
            {
                return;
            }

            FindNodeByIndex(root.LeftChild, ref index, ref nodeAtIndex);
            if (index == 0)
            {
                nodeAtIndex = root;
            }
            index--;
            FindNodeByIndex(root.RightChild, ref index, ref nodeAtIndex);
        }

        private void RemoveByNode(ref TreeNode node)
        {
            if (node.LeftChild == null && node.RightChild == null)
            {
                node = null;
                return;
            }

            if (node.LeftChild == null && node.RightChild != null)
            {
                node = node.RightChild;
                return;
            }

            if (node.LeftChild != null && node.RightChild == null)
            {
                node = node.LeftChild;
                return;
            }

            if (node.LeftChild != null && node.RightChild != null)
            {
                TreeNode smallestParent = this.FindSmallestNodeParent(node.RightChild);
                if (smallestParent == null)
                {
                    node.value = node.RightChild.value;
                    this.RemoveSemiNodeOrLeafByParent(node, ChildType.RightChild);
                    return;
                }
                else
                {
                    node.value = smallestParent.LeftChild.value;
                    this.RemoveSemiNodeOrLeafByParent(smallestParent, ChildType.LeftChild);
                    return;
                }
            }
        }

        private void RemoveSemiNodeOrLeafByParent(TreeNode parent, ChildType childType)
        {

            if (childType == ChildType.LeftChild)
            {
                TreeNode nodeToRemove = parent.LeftChild;
                if (nodeToRemove.LeftChild == null && nodeToRemove.RightChild == null)
                {
                    parent.LeftChild = null;
                }
                else
                {
                    if (nodeToRemove.LeftChild != null)
                    {
                        parent.LeftChild = nodeToRemove.LeftChild;
                    }
                    else
                    {
                        parent.LeftChild = nodeToRemove.RightChild;
                    }
                }
            }
            else
            {
                TreeNode nodeToRemove = parent.RightChild;
                if (nodeToRemove.LeftChild == null && nodeToRemove.RightChild == null)
                {
                    parent.RightChild = null;
                }
                else
                {
                    if (nodeToRemove.LeftChild != null)
                    {
                        parent.RightChild = nodeToRemove.LeftChild;
                    }
                    else
                    {
                        parent.RightChild = nodeToRemove.RightChild;
                    }
                }
            }
        }

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            for (int i = 0; i < this.count; i++)
            {
                yield return this[i];
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((IEnumerable<T>)this).GetEnumerator();
        }

        public override string ToString()
        {
            StringBuilder treeStringBuilder = new StringBuilder();
            for (int i = 0; i < this.count; i++)
            {
                string nodeValue = this[i].ToString();
                treeStringBuilder.Append(nodeValue);
                treeStringBuilder.Append(" ");
            }

            string treeAsString = treeStringBuilder.ToString();
            return treeAsString;
        }

        public override bool Equals(object obj)
        {
            BinarySearchTree<T> tree = obj as BinarySearchTree<T>;
            if (tree == null)
            {
                return false;
            }

            for (int i = 0; i < this.count; i++)
            {
                if (!this[i].Equals(tree[i]))
                {
                    return false;
                }
            }

            return true;
        }

        public override int GetHashCode()
        {
            int prime = 83;
            int hashCode = 0;

            for (int i = 0; i < this.count; i++)
            {
                hashCode += prime * this[i].GetHashCode();
            }

            return hashCode;
        }

        public static bool operator ==(BinarySearchTree<T> firstTree, BinarySearchTree<T> secondTree)
        {
            bool areEqual = firstTree.Equals(secondTree);
            return areEqual;
        }

        public static bool operator !=(BinarySearchTree<T> firstTree, BinarySearchTree<T> secondTree)
        {
            bool areEqual = firstTree.Equals(secondTree);
            return !areEqual;
        }

        public BinarySearchTree<T> Clone()
        {
            BinarySearchTree<T> treeClone = ((ICloneable)this).Clone() as BinarySearchTree<T>;
            return treeClone;
        }

        object ICloneable.Clone()
        {
            BinarySearchTree<T> treeClone = new BinarySearchTree<T>();
            foreach (var nodeValue in this)
            {
                treeClone.Add(nodeValue);
            }
            return treeClone;
        }
    }
}
